package 记忆化搜索;

import java.util.Arrays;


//        1 <= nums.length <= 20
//        0 <= nums[i] <= 1000
//        0 <= sum(nums[i]) <= 1000 //需要注意这个条件，这个指的是数组原本值的和，那么范围就应该是-1000到1000
//        -1000 <= target <= 1000

//494 目标和
public class Solution5 {
    public int findTargetSumWays(int[] nums, int target) {
        dp = new int[nums.length][2000];//两千就是根据题目条件的出来的，所以看题需要仔细！！！
        for(int i=0;i<nums.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return dfs(0,nums,target,0);
    }
    int[][] dp;//这里需要使用二维数组来记录状态，这个需要和dfs的变量参数进行统一
                //比如这题有两个变量，那么状态也需要两个参数才能记录唯一的一个状态
    int dfs(int index, int[]nums, int target, int cur){
        if(index == nums.length) return cur==target? 1:0;
        if(dp[index][cur+1000]!=-1) return dp[index][cur+1000];
        return dp[index][cur+1000] = dfs(index+1,nums,target,cur-nums[index])+dfs(index+1,nums,target,cur+nums[index]);
    }
}
